package com.zklh.leetcode.dynamic;

/**
 * @author ：tong nan
 * @date ：Created in 2021/10/10 11:54
 * @description ：石子游戏变种算法实现
 *  你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。
 * 石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1,100,3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。
 * 假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。
 * @modifiedBy ：
 */
public class Solution877 {

    private class Pair {
        int first;
        int second;

        @Override
        public String toString() {
            return "Pair{" +
                    "first=" + first +
                    ", second=" + second +
                    '}';
        }
    }

    int stoneGame(int[] piles) {
        // 定义dp 数组含义, dp[i][j] 表示 如果可选石子 是 piles 的 i->j,
        // 那么dp[i][j].first 存储先手拿石子的最大数量, dp[i][j].second为后手拿石子的最大数量
        // dp[i][j].first = Max(dp[i+1][j].second + piles[i], dp[i][j-1].second + piles[j])
        Pair[][] dp = new Pair[piles.length][piles.length];
        // 状态转移方程定义好后, 可选遍历方向有两种, 一种是自左向右, 向上遍历, 一种从左到右, 斜着遍历
        // 使用自左到右 向上遍历的方式
        // 初始化dp, 也就是中间线, i,i 值为 first = piles[i], second = 0;
        full(dp);
        for (int i = 0; i < piles.length; i++) {
            dp[i][i].first = piles[i];
        }
        // pilesPrefixSum[i] 表示 0, i-1 的前缀和, 则sum(i,j) = pilePrefixSum[j+1]-pilePrefixSum[i]
        int[] pilesPrefixSum = new int[piles.length+1];
        for (int i = 0; i < piles.length; i++) {
            pilesPrefixSum[i+1] = pilesPrefixSum[i] + piles[i];
        }

        int len = piles.length;
        for (int x = len-1; x >= 0; x--) {
            for (int y = x+1; y < len; y++) {
                dp[x][y].first = Math.max(dp[x+1][y].second + piles[x], dp[x][y-1].second+piles[y]);
                dp[x][y].second = pilesPrefixSum[y+1] - pilesPrefixSum[x] - dp[x][y].first;
            }
        }
        return dp[0][piles.length-1].first - dp[0][piles.length-1].second;
    }

    void full(Pair[][] pairs) {
        for (int i = 0; i < pairs.length; i++) {
            for (int j = 0; j < pairs[i].length; j++) {
                pairs[i][j] = new Pair();
            }
        }
    }

    public static void main(String[] args) {
        Solution877 solution = new Solution877();
        System.out.println(solution.stoneGame(new int[]{3,9,1,2}));
    }
}
